The invention is in the field of token ring systems, in which a token ring transmission network uni-directionally transmits data between terminals attached to the network by passing a data signal, termed a "token", which symbolizes authority to place data on the transmission network.
This invention particularly relates to a method and means for responding to loss of a token in a token ring network by choosing a leader terminal having the responsibility for regenerating the token and placing it on the transmission network.
Token ring systems are well understood in the art, and involve the use of a looped, uni-directional transmission system which connects a plurality of terminals for data exchange. A prior art token ring network is illustrated in FIG. 1 and consists of a set of receive/send (R/S) units 10, 12, 14, and 16, interconnected by uni-directional transmission links 10, 12; 12, 14; 14, 16; and 16, 10. The system is looped in that each send unit uni-directionally transmits over a respective link to the receive unit of one adjacent terminal. The receive unit's terminal has provision for providing the received information to the terminal's send unit so that the information is forwarded to the next adjacent terminal, and so on, until the information is eventually propagated around the ring, back to the receive unit of the originating terminal.
The prior art token ring system of FIG. 1 includes four terminals identified as a, d, s, and n, wherein the alphabetic character associated with each terminal also represents a unique identification code having a value with a magnitude which is relative to the magnitudes of the other terminals. In this regard, the identification code magnitudes of the prior art terminals of FIG. 1 have the relationship a&lt;d&lt;n&lt;s.
The system of FIG. 1 is a "token passing" system in that any one of the terminals a, d, n, s is enabled to place data on the token ring network when it obtains a signal having a unique bit pattern called a "token". In FIG. 1, the token is continuously circulated in a clockwise direction in the token ring network. When the token is received at a terminal having data available for transmission, the terminal inserts the data into the token, changes the token's configuration to indicate that it is unavailable, identifies itself and the terminal which is to receive the data, and retransmits the altered token on the token ring network.
The token is circulated on the token ring network until it arrives at the designated receiving terminal, where the data is read, and the token, once again, is forwarded. When the token arrives back at the sending terminal, the data is removed, and the token is altered to an available state and retransmitted on the ring.
Token passing protocols may vary, to some extent, from the procedure outlined above. However, all share the common characteristics of uni-directional transmission in a closed-looped transmission system to which access is obtained according to a protocol based upon a circulating token.
In token ring systems, a problem commonly arises when terminal failure or system noise obliterates or alters a circulating token. To recover synchronicity and reimplement the data transfer protocol, a new token must be generated to replace the lost or altered one. This can be done by designation of a master terminal having primary responsibility for token generation, system synchronization, and protocol oversight. Of course, if such a master terminal fails, the system will either fail totally or recover in a reduced-capacity state by transfer of master terminal duties to a subservient terminal.
In other token ring systems, system oversight and control is transferrable, with responsibility for token regeneration allocated according to a democratic procedure. In such systems, an algorithm or procedure is invoked to designate a "leader" terminal having responsibility for maintenance of a circulating token, and for regeneration of a lost or altered token.
Since a token ring network is intended to provide a high degree of communications availability, a token regeneration scheme must provide fast recovery from loss of a token in the form of speedy token regeneration. Preferably, token regeneration is preceded by selection of a leader terminal, following which the selected leader generates a new token. Implicit in this process is that leader selection be rapid, unambiguous, and as simple as possible.
The prior art procedures for token regeneration are based upon circulation of terminal identification codes in the event of token loss. In one procedure, all healthy terminals place their own identification codes on the token ring and forward all received identification codes. The first terminal to recognize its own code interrupts the procedure and generates the token. In another procedure, each terminal retransmits only identification codes having a predetermined magnitude relationship with its own identification code. Thus, for example, each terminal will retransmit only an identification code having a greater magnitude than its own. In this scheme, the first terminal receiving its identification code becomes the leader.